Mediocre String Problem （2018南京M,回文+LCP 3×3=9种做法 %%%千年好题 感谢"Grunt"大佬的细心讲解）

Diposting di | Edited on

题意

给出一个串S,和一个串T.

要求 从S串中取一个子串，后面接上T串的一个前缀 组成一个结果串，（要求S串的部分比T串的部分长）

其中，S串贡献的部分 可以分成两部分，S1+S2;

前面的S1 是T部分的反转；

S2 就只能是回文串，因为S串的部分必须比T的多，所以S2长度必须大于等于1

然后我们可以分成两部分，首先先把S中的所有回文串求出，可以用（回文树/马拉车/字符串哈希）

对于每一个回文串，它的左边半径部分都可以作为S1的右端点，除了中心，而且边缘也可以吃到一个

比如 CABABA 其中 回文串中心是第二个A，S1的右端点可以是CAB 注意C也可以的哦

然后找出这个端点剩下的就是求S1和T的lcp的长度了，根据题意每一个长度都一个贡献一个符合要求的答案

针对这个问题 我们可以把S 反转 和T用EXKMP 求lcp （也可以用后缀数组/字符串哈希/exkmp/后缀自动机）

所以 这题的解法大概有（3×3=9 或者3×4=12）种。

做法1 :马拉车+EXKMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
///感谢Grunt 大佬的细心讲解
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
char s[maxn],t[maxn];
int lens,lent;
int mynext[maxn];
int extend[maxn];
ll sum[maxn];
void pre_EKMP(char x[],int m,int next[]){
    next[0]=m;
    int j=0;
    while(j+1<m&&x[j]==x[j+1])j++;
    next[1]=j;
    int k=1;
    for(int i=2;i<m;i++){
        int p=next[k]+k-1;
        int L=next[i-k];
        if(i+L<p+1)next[i]=L;
        else{
            j=max(0,p-i+1);
            while(i+j<m&&x[i+j]==x[j])j++;
            next[i]=j;
            k=i;
        }
    }
}
void EKMP(char x[],int m,char y[],int n,int next[],int extend[]){
    pre_EKMP(x,m,next);
    int j=0;
    while(j<n&&j<m&&x[j]==y[j])j++;
    extend[0]=j;
    int k=0;
    for(int i=1;i<n;i++){
        int p=extend[k]+k-1;
        int L=next[i-k];
        if(i+L<p+1)extend[i]=L;
        else{
            j=max(0,p-i+1);
            while(i+j<n&&j<m&&y[i+j]==x[j])j++;
            extend[i]=j;
            k=i;
        }
    }
}
char Ma[maxn*2];
int Mp[maxn*2];
void Manacher(char s[],int len){
    int l=0;
    Ma[l++]='$';
    Ma[l++]='#';
    for(int i=0;i<len;i++){
        Ma[l++]=s[i];
        Ma[l++]='#';
    }
    Ma[l]=0;
    int mx=0,id=0;
    for(int i=0;i<l;i++){
        Mp[i]=mx>i?min(Mp[2*id-i],mx-i):1;
        while(Ma[i+Mp[i]]==Ma[i-Mp[i]])Mp[i]++;
        if(i+Mp[i]>mx){
            mx=i+Mp[i];
            id=i;
        }
    }
}
ll getsum(int l,int r){
    if(l>r)return 0;
    else if(l<=0)return sum[r];
    else return sum[r]-sum[l-1];
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>s>>t;
    lens=strlen(s);lent=strlen(t);
    Manacher(s,lens);
    reverse(s,s+lens);
    EKMP(t,lent,s,lens,mynext,extend);
    reverse(extend,extend+lens);
    sum[0]=extend[0];
    for(int i=1;i<lens;i++){
        sum[i]=sum[i-1]+extend[i];
    }
    ll ans=0;                                     ///0 1 2 3 4
    for(int i=2;i<2*lens+3;i++){                  ///a b a b a
        int cnt=Mp[i]-1;      ///6-1=5;            $ # a # b # a # b # a #
        if(cnt==0||Mp[i]==0)continue;           ///0 1 2 3 4 5 6 7 8 9 10 11
        if(cnt&1){///奇数长度的回文 例如ababa  MP= 1 1 2 1 4 1 6 1 4 1  2  1  0
            int where=(i-2)/2;  ///找到a这个位置 =(6-1)/2=2;
            int r=where-1;      ///然后从a前面一个位置b作为右端点 =1
            int l=where-Mp[i]/2; ///然后找到左端点=2-6/2 =-1
            ans+=getsum(l,r);
        }
        else{                 /// 偶数的  例如aabbaa
            int where=(i-2-1)/2;   /// 找到b#b中间的‘#’ 左边的b
            int r=where-1;         ///右端点
            int l=where-cnt/2;    /// 左端点
            ans+=getsum(l,r);
        }
    }
    cout<<ans<<endl;
    return 0;
}

做法2. 回文自动机+EXKMP

附上大佬的题解：

M.Mediocre String Problem

题意：给S串与T串。S[i..j]+T[1..k]为回文串，且|S[i..j]|>|T[1..k]|，求(i,j,k)个数。

将S[i..j]分为两个部分，S[i..p]为T[1..k]的反转，S[p+1..j]为回文串。

由于|S[i..j]|>|T[1..k]|，所以S[p+1..j]必须不为空。

枚举回文串的起始点p+1，那么我们要求的是：

1.由于S[i..p]为T[1..k]的反转，我们只要求有多少个(i,k)。这个部分是exkmp的基础。

将S反转，跟T跑exkmp，求出ex[]，再把ex[]反过来即可。

2.S[p+1..j]为回文串，我们只要求有多少个j，即求的是以p+1为起点的回文串个数cnt[]。

那么只要把S串倒着插入回文自动机，cnt[i]=插入第i个字符后，fail树的深度。

最后枚举回文串起点p+1，算出ex[p]*cnt[p+1]，求和即为答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
char s[maxn],t[maxn];
int lens,lent;
int mynext[maxn];
int extend[maxn];
int num[maxn];
void pre_EKMP(char x[],int m,int next[]){
    next[0]=m;
    int j=0;
    while(j+1<m&&x[j]==x[j+1])j++;
    next[1]=j;
    int k=1;
    for(int i=2;i<m;i++){
        int p=next[k]+k-1;
        int L=next[i-k];
        if(i+L<p+1)next[i]=L;
        else{
            j=max(0,p-i+1);
            while(i+j<m&&x[i+j]==x[j])j++;
            next[i]=j;
            k=i;
        }
    }
}
void EKMP(char x[],int m,char y[],int n,int next[],int extend[]){
    pre_EKMP(x,m,next);
    int j=0;
    while(j<n&&j<m&&x[j]==y[j])j++;
    extend[0]=j;
    int k=0;
    for(int i=1;i<n;i++){
        int p=extend[k]+k-1;
        int L=next[i-k];
        if(i+L<p+1)extend[i]=L;
        else{
            j=max(0,p-i+1);
            while(i+j<n&&j<m&&y[i+j]==x[j])j++;
            extend[i]=j;
            k=i;
        }
    }
}
struct Palindromic_Tree{
    int next[maxn][26];
    int fail[maxn];
    int cnt[maxn];
    int num[maxn];
    int len[maxn];
    int S[maxn];
    int last;
    int n;
    int p;
    int newnode(int l){
        for(int i=0;i<26;i++)next[p][i]=0;
        cnt[p]=num[p]=0;len[p]=l;
        return p++;
    }
    void init(){
        p=0;
        newnode(0);
        newnode(-1);
        last=n=0;
        S[n]=-1;
        fail[0]=1;
    }
    int getfail(int x){
        while(S[n-len[x]-1]!=S[n])x=fail[x];
        return x;
    }
    int add(int c){
        c-='a';
        S[++n]=c;
        int cur=getfail(last);
        if(!next[cur][c]){
            int now=newnode(len[cur]+2);
            fail[now]=next[getfail(fail[cur])][c];
            next[cur][c]=now;
            num[now]=num[fail[now]]+1;
        }
        last=next[cur][c];
        cnt[last]++;
        return num[last];
    }
    void count(){
        for(int i=p-1;i>=0;i--)cnt[fail[i]]+=cnt[i];
    }
}pam;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>s>>t;
    lens=strlen(s);lent=strlen(t);
    pam.init();
    for(int i=lens-1;i>=0;i--){
        num[i]=pam.add(s[i]);
    }
    reverse(s,s+lens);
    EKMP(t,lent,s,lens,mynext,extend);
    reverse(extend,extend+lens);
    ll ans=0;
    for(int i=0;i<lens-1;i++){
        ans+=1LL*extend[i]*num[i+1];
    }
    cout<<ans<<endl;
    return 0;
}

做法3.后缀数组+回文自动机（498ms)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
struct DA{
    #define F(x) ((x)/3+((x)%3==1?0:tb))
    #define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
    int sa[maxn*20],rank[maxn*20],height[maxn*20],str[maxn*20];
    int wa[maxn*20],wb[maxn*20],wv[maxn*20],wss[maxn*20];
    int c0(int *r,int a,int b){
        return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];
    }
    int c12(int k,int *r,int a,int b){
        if(k==2)
            return r[a]<r[b]||(r[a]==r[b]&&c12(1,r,a+1,b+1));
        else return r[a]<r[b]||(r[a]==r[b]&&wv[a+1]<wv[b+1]);
    }
    void sort(int *r,int *a,int *b,int n,int m){
        int i;
        for(i=0;i<n;i++)wv[i]=r[a[i]];
        for(i=0;i<m;i++)wss[i]=0;
        for(i=0;i<n;i++)wss[wv[i]]++;
        for(i=1;i<m;i++)wss[i]+=wss[i-1];
        for(i=n-1;i>=0;i--)
            b[--wss[wv[i]]]=a[i];
    }
    void dc3(int *r,int *sa,int n,int m){
        int i,j,*rn=r+n;
        int *san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;
        r[n]=r[n+1]=0;
        for(i=0;i<n;i++)if(i%3!=0)wa[tbc++]=i;
        sort(r+2,wa,wb,tbc,m);
        sort(r+1,wb,wa,tbc,m);
        sort(r,wa,wb,tbc,m);
        for(p=1,rn[F(wb[0])]=0,i=1;i<tbc;i++)
            rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;
        if(p<tbc)dc3(rn,san,tbc,p);
        else for(i=0;i<tbc;i++)san[rn[i]]=i;
        for(i=0;i<tbc;i++)if(san[i]<tb)wb[ta++]=san[i]*3;
        if(n%3==1)wb[ta++]=n-1;
        sort(r,wb,wa,ta,m);
        for(i=0;i<tbc;i++)wv[wb[i]=G(san[i])]=i;
        for(i=0,j=0,p=0;i<ta&&j<tbc;p++)
            sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
        for(;i<ta;p++)sa[p]=wa[i++];
        for(;j<tbc;p++)sa[p]=wb[j++];
    }
    void da(int n,int m){
        for(int i=n;i<n*3;i++)str[i]=0;
        dc3(str,sa,n+1,m);
        int i,j,k=0;
        for(i=0;i<=n;i++)rank[sa[i]]=i;
        for(i=0;i<n;i++){
            if(k)k--;
            j=sa[rank[i]-1];
            while(str[i+k]==str[j+k])k++;
            height[rank[i]]=k;
        }
    }
    void print(int n){
        cout<<"sa[] ";
        for(int i=0;i<=n;i++)cout<<sa[i]<<" ";cout<<endl;
        cout<<"rank[] ";
        for(int i=0;i<=n;i++)cout<<rank[i]<<" ";cout<<endl;
        cout<<"height[] ";
        for(int i=0;i<=n;i++)cout<<height[i]<<" ";cout<<endl;
    }
}DA;
struct PalTree{
    int next[maxn][26],fail[maxn],cnt[maxn],num[maxn],len[maxn],S[maxn],last,n,p;
    int newnode(int l){
        for(int i=0;i<26;i++)next[p][i]=0;
        cnt[p]=num[p]=0;len[p]=l;return p++;
    }
    void init(){
        p=0;newnode(0);newnode(-1);last=0;n=0;S[n]=-1;fail[0]=1;
    }
    int get_fail(int x){
        while(S[n-len[x]-1]!=S[n])x=fail[x];return x;
    }
    int add(int c){
        c-='a';S[++n]=c;int cur=get_fail(last);
        if(!next[cur][c]){
            int now=newnode(len[cur]+2);
            fail[now]=next[get_fail(fail[cur])][c];
            next[cur][c]=now;num[now]=num[fail[now]]+1;
        }
        last=next[cur][c];cnt[last]++;return num[last];
    }
    void count(){for(int i=p-1;i>=0;i--)cnt[fail[i]]+=cnt[i];}
}PAM;
char s[maxn],t[maxn];
int num[maxn],cnt[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>s>>t;
    int lens=strlen(s),lent=strlen(t);
    int len=0;PAM.init();
    for(int i=0;i<lens;i++)DA.str[len++]=s[lens-i-1]-'a'+1,cnt[lens-i-1]=PAM.add(s[lens-i-1]);
    DA.str[len++]=30;
    for(int i=0;i<lent;i++)DA.str[len++]=t[i]-'a'+1;
    DA.str[len]=0;
    DA.da(len,200);
	int p=DA.rank[lens+1];
	//DA.print(len);
	int now=len+1;
	for(int i=p-1;i>=0;i--){
		now=min(now,DA.height[i+1]);
		if(DA.sa[i]>=0&&DA.sa[i]<lens){
			num[lens-1-DA.sa[i]]=now;
		}
	}
	now=len+1;
	for(int i=p+1;i<=len;i++){
		now=min(now,DA.height[i]);
		if(DA.sa[i]>=0&&DA.sa[i]<lens){
			num[lens-1-DA.sa[i]]=now;
		}
	}
	ll ans=0;
    for(int i=0;i<lens-1;i++){
        ans+=1LL*num[i]*cnt[i+1];
    }
    cout<<ans<<endl;
    return 0;
}

感谢Grunt 大佬的细心讲解！！

///感谢Grunt 大佬的细心讲解

!(Mediocre String Problem/a.jpg)
毅种循环~
!(Mediocre String Problem/b.jpg)